L'automate (D'après BAC ES, Amérique du Nord 2019) - Corrigé

Énoncé

Pour accéder à un local d'une petite entreprise, les employés doivent choisir un code reconnu par l'automate suivant :

Une succession de lettres constitue un code possible si ces lettres se succèdent sur un chemin du graphe orienté ci-dessus, en partant du sommet n° 1 et en sortant au sommet n° 4.

Par exemple :

• le mot  $bcbab$  est un mot reconnu par cet automate, et correspond au chemin  $121334$  ;
• le mot  $abac$  n'est pas reconnu par cet automate.

1. Parmi les mots $abab,abc,abbcbb$ , quels sont ceux qui sont reconnus par cet automate ?

2. Écrire la matrice d'adjacence $A$  du graphe, en rangeant les sommets dans l'ordre croissant.

3. Quel est le nombre minimal de lettres d'un code possible ? Justifier.

4. Y a-t-il un nombre maximal de lettres d'un code possible ? Justifier.

5. On a calculé  $A^4=\left(\begin{array}{cccc}5& 3& 10& 5\\ 1& 6& 7& 4\\ 1& 3& 4& 2\\ 2& 1& 4& 2\end{array}\right)$  et  $A^5=\left(\begin{array}{cccc}3& 15& 18& 10\\ 6& 6& 14& 7\\ 3& 4& 8& 4\\ 1& 6& 7& 4\end{array}\right)$

    a. Combien y a-t-il de mots de quatre lettres qui conviennent ? Quels sont-ils ?
    b. Combien y a-t-il de mots de cinq lettres qui conviennent ?
    c. Pour varier les mots possibles, l'un des employés suggère de changer la programmation de l'automate pour utiliser dorénavant les chemins qui entrent au sommet n° 1 et sortent au sommet n° 2. Est-ce une bonne idée avec des mots de quatre lettres ? Avec des mots de deux lettres ?

$$ Solution

1. Le mot  $abab$  est reconnu (chemin  $12334$ ) ainsi que le mot  $abbcbb$  (chemin  $1234234$  ) mais le mot  $abc$  n'est pas reconnu. En effet, pour sortir au sommet n° 4, il faut terminer le mot par  $b$ .

2. La matrice d'adjacence de ce graphe est  $A=\left(\begin{array}{cccc}0& 2& 1& 0\\ 1& 0& 1& 0\\ 0& 0& 1& 1\\ 0& 1& 0& 0\end{array}\right)$

Cette matrice n'est pas symétrique car le graphe est orienté. Le coefficient  $a_{1,2}=2$  correspond aux deux arcs parallèles du sommet n° 1 vers le sommet n° 2.

3. Pour trouver le nombre minimal de lettres d'un mot, il faut calculer la distance entre les sommets n° 1 et n° 4. Pour cela, on peut calculer  $A^2$  dont le coefficient  $(1,4)$  vaut  $1$ , ou plus simplement on peut vérifier sur le graphe que le chemin  $134$  correspondant au mot  $bb$  permet de relier ces deux sommets.

4. Il n'y a pas de nombre maximal de lettres d'un mot, en raison de l'existence de cycles et même d'une boucle.

5. a. Le coefficient  $(1,4)$  de la matrice  $A^4$  vaut 5, il y a donc cinq chemins possibles :

• chemin  $12334$  qui donne  $abab$  ;
• chemin  $12334$  en utilisant l'arc parallèle entre les sommets n° 1 et n° 2 qui donne  $bbab$  ;
• chemin  $12134$  qui donne  $acbb$  ;
• chemin  $12334$  en utilisant l'arc parallèle entre les sommets n° 1 et n° 2 qui donne  $bcbb$  ;
• chemin  $13334$  qui donne  $baab$ . 

Tous ces mots sont différents donc il y a bien cinq mots possibles.

    b. Le coefficient  $(1,4)$  de la matrice  $A^5$  vaut 10, il y a donc dix chemins possibles :

• chemins  $123334$  qui donnent  $abaab$  ou  $bbaab$  ;
• chemins  $121334$  qui donnent  $acbab$  ou  $bcbab$  ;
• chemins  $121234$  qui donnent  $acabb$ ,  $acbbb$ ,  $bcabb$  ou  $bcbbb$  ;
• chemin  $134234$  qui donne  $bbcbb$  ;
• chemin  $133334$  qui donne  $baaab$ .

Tous ces mots sont différents donc il y a bien dix mots possibles. 

    c. Le coefficient  $(1,2)$  de la matrice  $A^4$  vaut 3, il y a donc seulement 3 chemins possibles, ce qui donnera au maximum 3 mots possibles.
Ce n'est donc pas une bonne idée si on fixe la longueur des mots à quatre lettres, bien que la dernière lettre possible en arrivant sur le sommet n° 2 soit  $a$  ou  $c$ , alors que seule  $c$  est possible en fixant l'arrivée au sommet n° 4.